This invention relates to a two-term vector multiplier for the efficient calculation of AX+BY.
A two-term vector multiplication (referred to as two-term multiplication hereunder) is a basic operation for the realization of spectrum analyzers using FFT (Fast Fourier Transform) for digital signal processing as well as for the realization of communication systems using digital filters.
For, instance, the FFT involves complex operations including complex multiplications shown below, and the real part and the imaginary part of such complex multiplication are calculated by the two-term multiplication: ##EQU1## where S.sub.R, S.sub.I and T.sub.r, T.sub.I represent the real and imaginary parts of S and T, respectively.
In the digital filter, the following operation including the two-term multiplication is always accomplished. Stated in detail, in view of the stability of coefficients for giving the characteristics to the digital filter, such filter is generally composed of a combination of second-order filters whose operations are represented by the following pair of equations: ##EQU2## where X.sub.i is the input data, y.sub.i ; the output data; and w.sub.i, the internal state of a second-order filter all at the sampling time i; and .alpha., .beta., .gamma. and .delta. are coefficients of the second-order filter. The parenthesized parts in Equation (2) are two-term multiplications.
The two-term multiplications are thus basic operations in the field of the digital signal processing, and their efficient calculation greatly contributes to improving the performance of digital signal processors.
For details of an FFT and Digital filters, reference is made to "Theory and Application of digital Signal Processing", by Lawrence R. Robiner et al, published by PRENTICE-HALL, Inc., 1975, pp. 356-437 and pp. 75-295, respectively.
To perform two-term multiplications using an FFT and/or digital filters on a real time basis, an arithmetic circuit with smaller power consumption and a high processing capability is needed. For this approach, a basic serial-parallel type-multiplier (referred to as basic multiplier) has been proposed in "Digital Computer Design Fundamentals", by Yaohan Chu published by McGraw-Hill Book Company, Inc., 1962, pp. 24-35. The operation principle of the basic multiplier is summarized as follows: Variables X and A are computed to give a product Z in the following manner: ##EQU3## with symbol ".alpha." indicating that a.sub.i is an element of set {0,1}. Equation (3) can also be solved by computing the following recursive formula, where n is the total bit number of variable A and suffix i represents the i-th recursive operation and the i-th bit position of variable A: ##EQU4##
A more improved example of the basic serial-parallel multiplier is the pipeline multiplier described in U.S. Pat. No. 3,885,141. This multiplier is intended to reduce the computing time per multiplication basic on the fact that the part corresponding to the number of bits of the multiplier on the LSB (least significant bit) side in the multiplication result is not used. As a result, the multiplication speed is doubled as compared with the basic multiplier by starting the next multiplication, upon completion of the LSB side operation of a first multiplication, while the MSB (most significant bit) side operation of the first multiplication is not finished. This multiplier, however, requires not only a complicated control but also a complicated structure in which six flip-flops are needed per adder for processing of each bit as is evident from FIG. 5.
Another upgraded serial-parallel multiplier is illustrated in FIG. 7 of U.S. Pat. No. 3,777,130. This multiplier uses an ROM (read only memory) and a circuit having approximately the same function as the basic multiplier to compute A.sub.1 x.sub.1 +A.sub.2 x.sub.2. . . A.sub.M x.sub.M in time equal to what the basic multiplier will take to accomplish a multiplication. This is due to the fact that the sum resulting from different combinations of coefficients A.sub.1, A.sub.2, . . . , A.sub.M are calculated and stored in the ROM in advance. Accordingly, this multiplier using the ROM is useful only when the coefficients A.sub.1, A.sub.2, . . . , A.sub.M are fixed, but not applicable to realize digital filters of different characteristics by the multiplex use of this multiplier on a time-sharing basis.